/**
 * 
 */
package string.passed;

import java.util.Arrays;

/**
 * @author xyyi
 *
 */
public class LongestSubstringWithoutRepeatingCharacters {

	/**
	  Given a string, find the length of the longest substring without repeating characters.
	  For example, the longest substring without repeating letters for "abcabcbb" is "abc",
	  which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
	 */
	// best for interview O(n)
	// 1 Traverse all chars in string
	// 2 a table to record the index for each char
	// 3 keep a start index without repeat until now
	// 4 update this start index with the repeat char's index + 1 when the repeat char index is greater or equal start index
	// 5 update table for each char's index
	// 6 compute current longest substring and update the global longest value   
	public int lengthOfLongestSubstring(String s) {
		if (s == null || s.isEmpty())
			return 0;

		int[] table = new int[256];
		Arrays.fill(table, -1);
		int start = 0; //start position till now without repeating
		int result = 0;
		for (int i = 0; i < s.length(); i++) {
			if (table[s.charAt(i)] >= start) // update index when find a repeat char and its index is greater than start
				start = table[s.charAt(i)] + 1;

			table[s.charAt(i)] = i;
			result = Math.max(result, i - start + 1);
		}

		return result;
	}

	public int lengthOfLongestSubstringGood(String s) {
		if (s == null || s.isEmpty())
			return 0;

		boolean[] table = new boolean[256];

		int first = 0, second = 0, max = 0;
		while (second < s.length()) {
			if (!table[s.charAt(second)]) {
				table[s.charAt(second)] = true;
				second++;
			} else {
				max = max < second - first ? second - first : max;
				while (s.charAt(first) != s.charAt(second)) {
					table[s.charAt(first)] = false;
					first++;
				}
				first++;
				second++;
			}
		}

		return max < second - first ? second - first : max;
	}

	/**
	 * 
	 */
	public LongestSubstringWithoutRepeatingCharacters() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
